package code;

import java.util.ArrayList;
import java.util.List;

public class Code95 {
	
	/*
	 * dfs(int s,int t,int TreeNode list)
	 * dfs 表示区间[s,t]产生的bst
	 * 
	 * @param s表示起点，t表示终点
	 * 
	 */
	
	public List<TreeNode> dfs(int s,int t){
		/*
		 * 只剩单个结点了
		 */
		List<TreeNode> list=new ArrayList<TreeNode>();
		if(s==t){
			list.add(new TreeNode(s));
			return list;
		}
		for(int i=s;i<=t;i++){
			//i结点作为第一个插入的点，作为父节点，将子树分成[s,i]与[i+1,t]子树
			List<TreeNode> leftTree=null;
			List<TreeNode> rightTree=null;
			if(s<i)
				leftTree=dfs(s,i-1);
			if(i<t)
				rightTree=dfs(i+1,t);
			/*
			 * 得到了左右子树，合并成以i为父节点的树
			 */
			if(leftTree==null){
				//左子树为空
				for(int j=0;j<rightTree.size();j++){
					TreeNode root=new TreeNode(i);
					root.right=rightTree.get(j);
					list.add(root);
				}
			}
			else{
				//左子树不为空
				//右子树为空
				if(rightTree==null)
				{
					for(int j=0;j<leftTree.size();j++){
						TreeNode root=new TreeNode(i);
						root.left=leftTree.get(j);
						list.add(root);
					}
				}
				//右子树不为空
				else{
					for(int j=0;j<leftTree.size();j++){
						for(int k=0;k<rightTree.size();k++){
							TreeNode root=new TreeNode(i);
							root.left=leftTree.get(j);
							root.right=rightTree.get(k);
							list.add(root);
						}
					}
				}
			}
			
		}
		return list;
	}
	
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> result=new ArrayList<TreeNode>();
        if(n>=1)
        	result=dfs(1,n);
        else{
        	result.add(null);
        }
        return result;
    }
    public static void main(String[] args){
    	Code95 code=new Code95();
    	code.generateTrees(0);
    }
}
